#include <iostream>
#include "queue/queue.h"

using namespace std;
#define INF 99999999

template <typename graph>
void traverse(graph& G){

	typename graph::adj_iterator j;

	for(int i = 1; i <= G.V(); i++ ){
        cout << i << ": ";
        for(j = G[i].begin(); j != G[i].end(); ++j){
            cout << (*j).first << "(" << (*j).second <<") ";
        }
        cout << endl;
	}

}

template <typename graph>
int dijkstra(graph& G, int start, int meta){

    queue *Q = new queue(G.V());
	int *d, *pi, u, v, w, i;
	
    typename graph::adj_iterator j;

	
	d = new int[G.V() + 1];
	pi = new int[G.V() + 1];

	for(i = 1; i <= G.V(); i++){ 
		d[i] = INF;
		pi[i] = 0;
		Q->insert(INF);
	}
	d[start] = 0;
    Q->decrease_value(start, 0);

    while(Q->size() != 1) {
		u = Q->min_key();
		Q->extract_min();
		for(j = G[u].begin(); j != G[u].end(); ++j){
			v = (*j).first;
			w = (*j).second;
			if( d[v] > d[u] + w){
				d[v] = d[u] + w;
				pi[v] = u;
				Q->decrease_value(v, d[v]);
			}
        }
    }

	meta = d[meta];
    delete [] d;
	delete [] pi;
	return  meta;
}

template <typename graph>
int bellman_ford(graph& G, int start, int meta){
	int  *d, *pi, i, u, v, w;
	
	typename graph::adj_iterator j;

	d = new int[G.V() + 1];
	pi = new int[G.V() + 1];

	for(i = 1; i <= G.V(); i++){ 
		d[i] = INF;
		pi[i] = 0;
	}
	d[start] = 0;

	for(i = 1 ; i < G.V(); i++){

		for(u = 1; u <= G.V(); u++){

			for(j = G[u].begin(); j != G[u].end(); ++j){
				v = (*j).first;
				w = (*j).second;
				if( d[v] > d[u] + w){
					d[v] = d[u] + w;
					pi[v] = u;
				}
			}
		}
	}

	meta = d[meta];
	delete [] d;
	delete [] pi;
	return  meta;
}













